package xyz.xiaotugou.algorithm;

/**
 * @author ysy
 * @version 1.0
 * @Title: 盛最多水的容器
 *          给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点(i,ai) 。在坐标内画 n 条垂直线，垂直线 i的两个端点分别为(i,ai)和(i, 0)。
 *          找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/container-with-most-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Note <b>ProjectName:</b> Pre-research
 * <br><b>PackageName:</b> xyz.xiaotugou.algorithm
 * <br><b>ClassName:</b> MaxArea
 * <br><b>Date:</b> 2022/1/11 12:39
 */
public class MaxArea {


    /**
     * @Author ysy
     * @Description 暴力法：双层for循环笨方法 【O(n^2)】
     * @Date 2022/1/11 13:37
     * @Param 
     * @return int
     **/
    public static int maxArea(int[] heights){
        int maxArea = 0;
        for(int i=0; i<heights.length; i++){
            for(int j=i+1; j<heights.length; j++){
                maxArea = Math.max(maxArea, (j-i)*Math.min(heights[i], heights[j]));
            }
        }
        return maxArea;
    }

    /**
     * @Author ysy
     * @Description
     *              双指针法 【O(n)】
     *              核心优化思路：
     *                  - 从两边往中间移动时，宽度下降，那高度比外侧短的棒棒不用考虑(面积一定小)
     *                  - 单次for循环：左右两侧，谁矮谁往中间移动
     * @Date 2022/1/11 22:07
     * @Param 
     * @return int
     **/
    public static int maxArea1(int[] heights) {
        int maxArea = 0;
        for(int i=0, j=heights.length-1; i < j;){
            // 获取高度值【同时，谁小谁往中间移】: heights[i] > heights[j] ? heights[j--] : heights[i++]
            // 宽：j-i
            maxArea = Math.max(maxArea, (j-i) * (heights[i] > heights[j] ? heights[j--] : heights[i++]));
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] heights = {1,8,6,2,5,4,8,3,7};
        System.out.println("最大面积：" + maxArea(heights));
        System.out.println("最大面积：" + maxArea1(heights));
    }
}
